home *** CD-ROM | disk | FTP | other *** search
- /*
- *
- * B G _ M O V E . C , moving and placing the pieces
- * O.F.Ransen: 21st June 1991
- * This version: 30th May 1992
- *
- */
-
- #include <stdlib.h>
- #include <stdio.h>
- #include <conio.h>
- #include <string.h>
- #include "bg.h"
-
- /***************************************************************************/
-
- char Globerr[GERR_LEN] = "" ;
-
- const Layout_t Initial_Layout = {0, /* the bar */
- 2,0,0,0,0,0, /* two runners */
- 0,0,0,0,0,5,
- 0,0,0,0,3,0,
- 5,0,0,0,0,0, /* home */
- 0} ;
-
- void Initial_Board (Layout_t Layouts[2])
- /*
- PURPOSE: To initial the layouts to the start of a game.
- */
- {
- short p ;
- for (p = 0 ; p < N_PLACES ; p++) {
- Layouts [BLACK_PLAYER][p] = Initial_Layout [p] ;
- Layouts [WHITE_PLAYER][p] = Initial_Layout [p] ;
- }
- }
-
- /*************************************************************************/
-
- void Select_Best_Move (Dice_t* The_Dice,
- Layout_t My_Old, Layout_t His_Old,
- Transit_t* My_Best_Tr, Transit_t* His_Best_Tr,
- Player_t Player, Search_t Search)
- /*
- PURPOSE: Given the current situation and the two Dice I return
- with the best move possible contained in the
- new layouts.
- NOTES: 1) The Transit_t returned show us the new Layouts and how
- we got there.
- 2) If the search type is Max_Only then we are just searching
- for the largest number of moves possible, and when we find it
- we can stop searching.
- */
- {
- Transit_t My_Old_Tr,His_Old_Tr ;
-
- (void)strcpy (Globerr,"Select_Best_Move 1") ;
-
- Init_Transit (My_Best_Tr,My_Old) ;
- Init_Transit (His_Best_Tr,His_Old) ;
-
- Copy_Transit (&My_Old_Tr,My_Best_Tr) ;
- Copy_Transit (&His_Old_Tr,His_Best_Tr) ;
-
- if (The_Dice->N_Vals == 4) {
- /* No problems with order of moves, all 4 the same */
- Lay_Sel_t Best_Score ;
-
- Best_Score.Goodness = WORST_SCORE ;
- Best_Score.Moves_Made = WORST_SCORE ;
- Select_Best_Ndice_Move (The_Dice,3,
- &My_Old_Tr,&His_Old_Tr,
- My_Best_Tr,His_Best_Tr,
- &Best_Score,Player,Search) ;
-
- } else if (The_Dice->N_Vals == 2) {
- /* Problems with order */
- Select_Best_2Dice_Move (The_Dice,
- &My_Old_Tr,&His_Old_Tr,
- My_Best_Tr,His_Best_Tr,Player) ;
- } else {
- Error_Exit ("The_Dice->N_Vals very strange...") ;
- }
-
- Check_Layout (My_Best_Tr->Layout, "Checking Mine_New") ;
- Check_Layout (His_Best_Tr->Layout,"Checking His_New") ;
- (void)strcpy (Globerr,"Select_Best_Move 2") ;
- }
-
- /*************************************************************************/
-
- void Select_Best_2Dice_Move (Dice_t* The_Dice,
- Transit_t* My_Old_Tr, Transit_t* His_Old_Tr,
- Transit_t* My_Best_Tr, Transit_t* His_Best_Tr,
- Player_t Player)
- /*
- PURPOSE: To select the best move trying first Dice_AB and then Dice_BA
- sequence.
- NOTES: 1) If we see we are at the opening move of the game then we
- do one of the standard moves contained in BG_STDOP.C
- */
- {
- Transit_t My_AB,My_BA,His_AB,His_BA ;
- Lay_Sel_t Best_Score_AB,Best_Score_BA ;
- boolean Copy_AB,Copy_BA ;
- char Temp ;
-
- (void)strcpy (Globerr,"Select_Best_2Dice_Move 1") ;
-
- if (Standard_Opening (The_Dice,
- My_Old_Tr, His_Old_Tr,
- My_Best_Tr, His_Best_Tr)) {
- return ;
- }
-
- Copy_Transit (&My_AB,My_Old_Tr) ;
- Copy_Transit (&My_BA,My_Old_Tr) ;
- Copy_Transit (&His_AB,His_Old_Tr) ;
- Copy_Transit (&His_BA,His_Old_Tr) ;
-
- Best_Score_AB.Goodness = WORST_SCORE ;
- Best_Score_AB.Moves_Made = WORST_SCORE ;
- Select_Best_Ndice_Move (The_Dice,1,
- My_Old_Tr,His_Old_Tr,
- &My_AB,&His_AB,
- &Best_Score_AB,Player,Bestest) ;
-
- (void)strcpy (Globerr,"Select_Best_2Dice_Move 2") ;
-
- /* Swap dice order... */
- Temp = The_Dice->Values[0] ;
- The_Dice->Values[0] = The_Dice->Values[1] ;
- The_Dice->Values[1] = Temp ;
-
- Best_Score_BA.Goodness = WORST_SCORE ;
- Best_Score_BA.Moves_Made = WORST_SCORE ;
- Select_Best_Ndice_Move (The_Dice,1,
- My_Old_Tr,His_Old_Tr,
- &My_BA,&His_BA,
- &Best_Score_BA,Player,Bestest) ;
-
- (void)strcpy (Globerr,"Select_Best_2Dice_Move 3") ;
-
- if (Best_Score_AB.Moves_Made > Best_Score_BA.Moves_Made) {
- Copy_AB = TRUE ;
- Copy_BA = FALSE ;
- } else if (Best_Score_BA.Moves_Made > Best_Score_AB.Moves_Made) {
- Copy_BA = TRUE ;
- Copy_AB = FALSE ;
- } else if (Best_Score_BA.Moves_Made != 0) {
- /* Moves_Made are equal and non zero in both cases, choose the best */
- if (Best_Score_AB.Goodness > Best_Score_BA.Goodness) {
- Copy_AB = TRUE ;
- Copy_BA = FALSE ;
- } else {
- Copy_BA = TRUE ;
- Copy_AB = FALSE ;
- }
- } else {
- Copy_BA = FALSE ;
- Copy_AB = FALSE ;
- }
-
- (void)strcpy (Globerr,"Select_Best_2Dice_Move 4") ;
-
- if (Copy_AB) {
- Copy_Transit (My_Best_Tr,&My_AB) ;
- Copy_Transit (His_Best_Tr,&His_AB) ;
- } else if (Copy_BA) {
- Copy_Transit (My_Best_Tr,&My_BA) ;
- Copy_Transit (His_Best_Tr,&His_BA) ;
- }
-
- (void)strcpy (Globerr,"Select_Best_2Dice_Move 5") ;
- }
-
- /*************************************************************************/
-
- void Select_Best_Ndice_Move (Dice_t* Dice_List, short This_Dice,
- Transit_t* My_Curr_Tr, Transit_t* His_Curr_Tr,
- Transit_t* My_Best_Tr, Transit_t* His_Best_Tr,
- Lay_Sel_t* Best_Score, Player_t Player,
- Search_t Search)
- /*
- PURPOSE: To select the best or most legal move so far.
- NOTES : 1) If Depth_Only then we don't care about the goodness of the
- move, only the legality of it. And we stop searching as soon
- as we have found a legal move of 4, the maximum possible.
- 2) If This_Dice = -1 then we have stopped recursion, obviously
- */
- {
- static short Moves_Done = 0 ;
-
- if (Won (My_Best_Tr->Layout,His_Best_Tr->Layout) > NO_WIN) {
- return ;
- }
-
- #if DEBUG_SOURCE
- (void)strcpy (Globerr,"Select_Best_Ndice_Move 1") ;
- Check_Layout (My_Curr_Tr->Layout,"Checking My_Curr_Tr") ;
- Check_Layout (His_Curr_Tr->Layout,"Checking His_Curr_Tr") ;
- if (This_Dice > 3) {
- printf ("\nInvalid Dice value: %d",This_Dice) ;
- Error_Exit ("Invalid Dice value") ;
- }
- #endif
-
- if (This_Dice >= 0) {
- char p ;
- boolean Something_Moved ;
-
- Something_Moved = FALSE ;
- for (p = BAR_I ; p <= POINT24_I ; p++) {
- if (Can_Move (p,Dice_List->Values[This_Dice],
- My_Curr_Tr->Layout,His_Curr_Tr->Layout)) {
- /* It is ok to move from 'p' with this dice value */
- Transit_t My_Temp,His_Temp ;
-
- Something_Moved = TRUE ;
- Copy_Transit (&My_Temp,My_Curr_Tr) ;
- Copy_Transit (&His_Temp,His_Curr_Tr) ;
-
- Execute_Move (p,Dice_List->Values[This_Dice],
- &My_Temp,&His_Temp) ;
-
- Moves_Done++ ;
- if (Moves_Done > 4) {
- Error_Exit ("Moves_Done > 4") ;
- }
- (void)strcpy (Globerr,"Select_Best_Ndice_Move 2") ;
-
- /* Recurse... */
- Select_Best_Ndice_Move (Dice_List, This_Dice-1,
- &My_Temp,&His_Temp,
- My_Best_Tr,His_Best_Tr,
- Best_Score,Player,Search) ;
- Moves_Done-- ;
- }
- }
- if (!Something_Moved) {
- /* No more moves possible in this branch, end recursion
- and choose a move. */
- (void)strcpy (Globerr,"Select_Best_Ndice_Move 3") ;
- Choose_Move (My_Curr_Tr, His_Curr_Tr,
- Player,Moves_Done,
- My_Best_Tr,His_Best_Tr,Best_Score,Search) ;
- }
- if (Moves_Done < 0) {
- Error_Exit ("Moves < 0 ") ;
- }
- } else {
- /* No more dice, see if this any better than previous best */
- if ((Search == Legalest) && (Best_Score->Moves_Made == 4)) {
- /* No more choosing to do, we already know the maximum number
- of moves to do */
- return ;
- }
- Choose_Move (My_Curr_Tr,His_Curr_Tr,
- Player,Moves_Done,
- My_Best_Tr,His_Best_Tr,Best_Score,Search) ;
-
- }
- }
-
- /*************************************************************************/
-
- void Choose_Move (Transit_t* Mine, Transit_t* His,
- Player_t Player, short Moves_Done,
- Transit_t* My_Best, Transit_t* His_Best,
- Lay_Sel_t* Best_Score, Search_t Search)
- /*
- PURPOSE: We have to choose between two moves, the previous best and
- the one handed to us here.
- NOTES: 1) We change the best variables to this one if it is better.
- 2) The number of moves made takes precedence over the goodness
- of the move. According to the rules of Backgammon you must
- make the most moves possible.
- 3) Usually this is the function called at the end of a recursive
- branch.
- 4) If the search type is just looking for max moves then we do
- not evaluate the move, just look at the Moves_Done, to get
- a legal move.
- */
- {
- boolean Copy ;
- long Goodness ;
-
- (void)strcpy (Globerr,"Choose_Move 1") ;
-
- if (Search == Bestest) {
- Goodness = Evaluate_Move (Mine->Layout,His->Layout,Player) ;
- } else if (Search == Legalest) {
- Goodness = 0 ;
- } else {
- Error_Exit ("Bad Search value in Choose_Move") ;
- }
- if (Moves_Done < Best_Score->Moves_Made) {
- Copy = FALSE ; /* The best move so far has moved more pieces than
- this current move, so do not change the best move. */
- } else {
- if (Goodness > (Best_Score->Goodness)) {
- /* An obviously better move */
- Copy = TRUE ;
- } else if (Goodness == (Best_Score->Goodness)) {
- /* Choose at random between the two equal valued moves */
- Copy = (Int_Rand_Range (0,100) > 50) ;
- } else {
- /* Not at all a good move */
- Copy = FALSE ;
- }
- }
- if (Copy) {
- Copy_Transit (My_Best,Mine) ;
- Copy_Transit (His_Best,His) ;
- Best_Score->Goodness = Goodness ;
- Best_Score->Moves_Made = Moves_Done ;
- }
- }
-
- /*************************************************************************/
-
- void Execute_Move (char p, char Die, Transit_t* Mine, Transit_t* His)
- /*
- PURPOSE: To move a piece from point p Die spaces forward. We will
- eat one of his pieces if there is one. We record the new layouts
- and move made in the transit types.
- */
- {
- char New_Point,His_Point,Places_Moved ;
-
- New_Point = p + Die ;
- if (New_Point > HOME_I) {
- Places_Moved = Die - (New_Point - HOME_I) ;
- New_Point = HOME_I ;
- } else {
- Places_Moved = Die ;
- }
- His_Point = Reverse_Index(New_Point) ;
-
- #if DEBUG_SOURCE
- if (Mine->Layout[p] < 1) {
- Error_Exit ("Trying to move a piece from an empty point") ;
- } else if ((His->Layout[His_Point] > 1) && (New_Point != HOME_I)){
- Error_Exit ("Trying to move a piece to a blocked point") ;
- }
- #endif
-
- /* Move my piece in the layout */
- Mine->Layout [p]-- ;
- Mine->Layout [New_Point]++ ;
-
- /* Record how the transit was made */
- Mine->Old_Points [Mine->N_Moves] = p ;
- Mine->Places_Movd[Mine->N_Moves] = Places_Moved ;
-
- /* Remember that Row is number of pieces-1 */
- Mine->Old_Row [Mine->N_Moves] = Mine->Layout[p] ;
- Mine->New_Row [Mine->N_Moves] = Mine->Layout[New_Point]-1 ;
- Mine->N_Moves++ ;
-
- /* Eat his piece ? ... */
- if ((His_Point != BAR_I) && (His_Point != HOME_I)) {
- if (His->Layout[His_Point] == 1) {
-
- /* Move the point eaten back to the bar */
- His->Layout[His_Point] = 0 ;
- His->Layout[BAR_I]++ ;
-
- /* Record how his piece moved back to the bar */
- His->Old_Points [His->N_Moves] = His_Point ;
- His->Places_Movd[His->N_Moves] = BAR_I - His_Point ;
- His->Old_Row [His->N_Moves] = 0 ;
- His->New_Row [His->N_Moves] = His->Layout[BAR_I]-1 ;
- His->N_Moves++ ;
- } else {
- His->N_Moves = 0 ;
- }
- } else {
- His->N_Moves = 0 ;
- }
- }
-
- /*************************************************************************/
-
- boolean Can_Move (char p, char Die, Layout_t Me, Layout_t Him)
- /*
- PURPOSE: To return TRUE if a move is possible.
- */
- {
- short New_Point ;
-
- if (Me[p] == 0) {
- /* I have no pieces on this point */
- return (FALSE) ;
- }
-
- New_Point = p+Die ;
- if (New_Point > HOME_I) {
- /* The new point would be home */
- New_Point = HOME_I ;
- }
-
- if ((Him[Reverse_Index(New_Point)] > 1) && (New_Point != HOME_I)) {
- /* He is occupying where I would have gone */
- return (FALSE) ;
- }
-
- if (New_Point == HOME_I) {
- /* I want to go home... */
- if (!Bearing_Off(Me)) {
- /* ...but I am not bearing off. */
- return (FALSE) ;
- } else if ((p+Die) == HOME_I) {
- /* ...and can move exactly to home */
- return (TRUE) ;
- } else if (Pieces_Behind(Me,p)) {
- /* ...but pieces behind me, so cannot take piece home. */
- return (FALSE) ;
- }
- }
-
- if ((p != BAR_I) && (Me[BAR_I] != 0)) {
- /* Trying to move a non bar piece while still on bar */
- return (FALSE) ;
- }
-
- return (TRUE) ;
- }
-
- /*************************************************************************/
-
- void Copy_Layout (Layout_t Dst, Layout_t Src)
- /*
- PURPOSE: To copy the Src to the Dst.
- */
- {
- ushort p ;
-
- for (p = 0 ; p < N_PLACES ; p++) {
- Dst[p] = Src[p] ;
- }
- }
-
- /*************************************************************************/
-
- boolean Bearing_Off (Layout_t Lay)
- /*
- PURPOSE: To return TRUE if all the pieces on the layout are in the
- final quadrant.
- */
- {
- ushort p ;
-
- p = BAR_I ;
- do {
- if (Lay[p] != 0) {
- return (FALSE) ;
- }
- p++ ;
- } while (p < 19) ;
-
- return (TRUE) ;
- }
-
- /*************************************************************************/
-
- short Won (Layout_t Me, Layout_t Him)
- /*
- PURPOSE: To return 0,SIMPLE,GAMMON or BACKGAMMON according to the layout.
- */
- {
- short p ;
- if (Me[HOME_I] == N_PIECES) {
- /* We have won, now work out by how much */
- if (Him[HOME_I] > 0) {
- /* He has taken off at least one piece */
- return (SIMPLE) ;
- } else {
- /* It all depends on where is the last piece */
- for (p = BAR_I ; p < HOME_I ; p++ ) {
- if (Him[p] > 0) {
- break ;
- }
- }
- if (p < 7) {
- /* He has a piece in my inner table */
- return (BACKGAMMON) ;
- } else {
- return (GAMMON) ;
- }
- }
- } else {
- return (NO_WIN) ;
- }
- }
-
- /*************************************************************************/
-
- boolean Pieces_Behind (Layout_t Me, short p)
- /*
- PURPOSE: To return TRUE if there are any of my pieces further behind than
- p.
- */
- {
- p-- ;
- while (p >= 0) {
- if (Me[p]) {
- return (TRUE) ;
- }
- p-- ;
- }
- return (FALSE) ;
- }
-
- /*************************************************************************/
-
- void Check_Layout (Layout_t Layout, char* Err_Mess)
- /*
- PURPOSE: To check that the layout is legal, exiting with an
- error message if it is not.
- */
- {
- short Total,p ;
- Total = 0 ;
- for (p = BAR_I ; p < N_PLACES ; p++) {
- Total = Total + Layout[p] ;
- }
- if (Total != N_PIECES) {
- printf ("\nERROR: Total = %d",(int)Total) ;
- printf ("\n ") ;
- for (p = 0 ; p < N_PLACES ; p++) {
- printf ("%3d",p) ;
- }
- printf ("\nM") ;
- for (p = 0 ; p < N_PLACES ; p++) {
- printf ("%3d",Layout[p]) ;
- }
- Error_Exit (Err_Mess) ;
- }
- }
-
- /*************************************************************************/
-
- void Copy_Transit (Transit_t* Dest, Transit_t* Source)
- /*
- PURPOSE: To copy the source transit into the destination transit
- */
- {
- short m ;
-
- #if DEBUG_SOURCE
- if ((Source->N_Moves > 4) || (Source->N_Moves < 0)) {
- printf ("\nCopy_Transit, N_Moves = %d",Source->N_Moves) ;
- Error_Exit ("bad N_Moves in Copy_Transit") ;
- }
- #endif
-
- Copy_Layout (Dest->Layout,Source->Layout) ;
- Dest->N_Moves = Source->N_Moves ;
- for (m = 0 ; m < Dest->N_Moves ; m++) {
-
- #if DEBUG_SOURCE
- if ((Source->Old_Points[m] + Source->Places_Movd[m]) > HOME_I) {
- printf ("\nERROR Points[%d]=%d Source->Places_Movd[%d]",
- m,Source->Old_Points[m] + Source->Places_Movd[m],m) ;
- Error_Exit ("in Copy_Transit Old+Places_Moved > HOME_I") ;
- }
- #endif
-
- Dest->Old_Points [m] = Source->Old_Points [m] ;
- Dest->Places_Movd [m] = Source->Places_Movd [m] ;
- Dest->Old_Row [m] = Source->Old_Row [m] ;
- Dest->New_Row [m] = Source->New_Row [m] ;
- }
- }
-
- /*************************************************************************/
-
- void Init_Transit (Transit_t* New, Layout_t Old)
- /*
- PURPOSE: To copy the Old layout into the transit and init everything
- else to zero.
- */
- {
- Copy_Layout (New->Layout,Old) ;
- New->N_Moves = 0 ;
- }
-
- /*************************************************************************/
-
- boolean Move_Possible (Layout_t P_Lay, Layout_t O_Lay)
- /*
- Returns TRUE if the the Players layout is not completly blocked by
- the Opponents layout.
- */
- {
-
- if (P_Lay [BAR_I] == 0) {
- return (TRUE) ;
- } else {
- /* The player has a piece on the bar, has the opponent blocked
- all six entry points? */
- short p ;
- for (p = 19 ; p <= POINT24_I ; p++) {
- if (O_Lay[p] < 2) {
- return (TRUE) ; /* ...no, we can get out here */
- }
- }
- return (FALSE) ; /* .. yes, all six blocked */
- }
- }
-
- /*************************************************************************/
-
-